package com.adt;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyLinkedList<T> implements Iterable<T> {

	private int theSize;

	private int modCount = 0;

	private Node<T> beginMarker;

	private Node<T> endMarker;

	private static class Node<T> {
		public T data;
		public Node<T> prev;
		public Node<T> next;

		public Node(T d, Node<T> p, Node<T> n) {
			data = d;
			prev = p;
			next = n;
		}
	}

	public MyLinkedList() {
		clear();
	}

	public void clear() {
		beginMarker = new Node<T>(null, null, null);
		endMarker = new Node<T>(null, beginMarker, null);
		beginMarker.next = endMarker;
		theSize = 0;
		modCount++;
	}

	public int size() {
		return theSize;
	}

	public boolean isEmpty() {
		return size() == 0;
	}

	public boolean add(T x) {
		add(size(), x);
		return true;
	}

	public boolean add(int idx, T x) {
		addBefore(getNode(idx), x);
		return true;
	}

	public T get(int idx) {
		return getNode(idx).data;
	}

	public T set(int idx, T newValue) {
		Node<T> p = getNode(idx);
		T oldValue = p.data;
		p.data = newValue;
		return oldValue;
	}

	public T remove(int idx) {
		return remove(idx);
	}
	
	public void swap(int idx1,int idx2){
		if(idx1<0||idx1>size()){
			throw new IndexOutOfBoundsException();
		}
		
		if(idx2<0||idx2>size()){
			throw new IndexOutOfBoundsException();
		}
		
		Node<T> node1 = getNode(idx1);
		Node<T> node2 = getNode(idx2);
		
		node1.prev.next = node2;
		node2.prev = node1.prev;
		
		node1.next = node2.next;
		node2.next.prev = node1;
		
		node2.next = node1;
		node1.prev = node2;
	}

	@Override
	public Iterator<T> iterator() {
		
		return new LinkedListIterator();
	}

	/**
	 * 
	 * @param p
	 * @param x
	 */
	private void addBefore(Node<T> p, T x) {
		Node<T> newNode = new Node<T>(x, p.prev, p);
		newNode.prev.next = newNode;
		p.prev = newNode;
		theSize++;
		modCount++;
	}

	private T remove(Node<T> p) {
		p.next.prev = p.prev;
		p.prev.next = p.next;
		theSize--;
		modCount++;
		return p.data;
	}

	/**
	 * @param idx
	 * @return
	 */
	private Node<T> getNode(int idx) {
		Node<T> p;
		if (idx < 0 || idx > size()) {
			throw new IndexOutOfBoundsException();
		}

		if (idx < size() / 2) {
			p = beginMarker.next;
			for (int i = 0; i < idx; i++) {
				p = p.next;
			}
		} else {
			p = endMarker;
			for (int i = size(); i > idx; i--) {
				p = p.prev;
			}
		}
		return p;
	}
	
	private class LinkedListIterator implements Iterator<T>{
		
		private Node<T> current = beginMarker.next;
		
		private int expectedModCount = modCount;
		
		private boolean okToRemove = false;
		

		@Override
		public boolean hasNext() {
			return current!=endMarker;
		}

		@Override
		public T next() {
			if(modCount!=expectedModCount){
				throw new ConcurrentModificationException();
			}
			
			if(!hasNext()){
				throw new NoSuchElementException();
			}
			
			T nextItem = current.data;
			current = current.next;
			okToRemove = true;
			return nextItem;
		}
		
		public void remove(){
			if(modCount!=expectedModCount){
				throw new ConcurrentModificationException();
			}
			
			if(!okToRemove){
				throw new IllegalStateException();
			}
			
			MyLinkedList.this.remove(current.prev);
			okToRemove = false;
			expectedModCount++;
		}
		
	}

}
